package com.mgq.algorithm;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author MaGuangQi
 * @description: 用队列实现栈 225题,解法二: 使用一个队列实现
 * https://leetcode-cn.com/problems/implement-stack-using-queues/
 * @date 2020-06-15 19:04
 **/
public class QueueGenStack2 {
    LinkedList<Integer> list = new LinkedList<>();
    public QueueGenStack2() {

    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        list.add(x);
     int   size = list.size();
        while (size > 1) {
            //每次把头元素添加到队尾
            //第一次 1
            //第二次 1 2
            //转换后 2  1

            //第二次  2  1 3
            //循环 移除头 1 3 2
            //移除头 3 2 1
            list.add(list.remove());
            size--;
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        if (list.isEmpty()) {
            throw new RuntimeException("没有元素");
        }

        return  list.remove();

    }

    /**
     * Get the top element.
     */
    public int top() {
        return list.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return list.isEmpty();
    }

    public static void main(String[] args) {
        QueueGenStack2 stack = new QueueGenStack2();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("栈顶"+stack.top());
        System.out.println(stack.pop());
        System.out.println("栈顶"+stack.top());
        System.out.println(stack.pop());
        System.out.println("栈顶"+stack.top());
        System.out.println(stack.pop());
    }
}
